package com.likou.second_challenge;

import java.util.Deque;
import java.util.LinkedList;

public class q19 {

    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode p1 = head;
        ListNode p2 = head;
        for (int i = 0; i < n; i++) {
            p2 = p2.next;
        }

        if (p2 == null) {
            return head.next;
        }
        p2 = p2.next;
        while (p2 != null) {
            p1 = p1.next;
            p2 = p2.next;
        }

        p1.next = p1.next.next;
        return head;
    }

//    public ListNode removeNthFromEnd(ListNode head, int n) {
//        Deque<ListNode> deque = new LinkedList<>();
//        ListNode p = head;
//        while (p != null) {
//            deque.push(p);
//            p = p.next;
//        }
//
//        for (int i = 0; i < n; i++) {
//            deque.poll();
//        }
//
//        ListNode peek = deque.peek();
//        if (peek != null) {
//            peek.next = peek.next.next;
//        } else {
//            head = head.next;
//        }
//
//        return head;
//    }
}
